﻿#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<map>
#include<set>
#include<algorithm>
#include<vector>
#include<string>
#include<string.h>
#include <math.h>
#include <unordered_map>
#include <unordered_set>
using namespace std;

//aaaaa
//end
//end 
//end end

#if 0
#include <iostream>
using namespace std;

int ret = 0;

void dfs(int k, int a, int b)
{
	if (k > 7)
	{
		if (a == 0 && b == 0)
		{
			ret++;
		}
		return;
	}

	for (int i = 0; i <= a; i++)
	{
		for (int j = 0; j <= b; j++)
		{
			if (i + j >= 2 && i + j <= 5)
			{
				dfs(k + 1, a - i, b - j);
			}
		}
	}
}

int main()
{
	dfs(1, 9, 16);
	cout << ret << endl;
	return 0;
}
#endif


/*
#include <iostream>
using namespace std;

int ret = 0;

void dfs(int s1, int s2, int a, int b, int c, int d, int e, int f, int g)
{
	if (a > 7 || b > 7 || c > 7 || d > 7 || e > 7 || f > 7 || g > 7)
	{
		return;
	}

	if (s1 < 0 || s2 < 0)
	{
		return;
	}

	if (s1 == 0 && s2 == 0)
	{
		if (a >= 2 && a <= 5 && b >= 2 && b <= 5 && c >= 2 && c <= 5 && d >= 2 && d <= 5 && e >= 2 && e <= 5 && f >= 2 && f <= 5 && g >= 2 && g <= 5)
		{
			ret++;
		}

		return;
	}

	// 分第一种糖果
	dfs(s1 - 1, s2, a + 1, b, c, d, e, f, g);
	dfs(s1 - 1, s2, a, b + 1, c, d, e, f, g);
	dfs(s1 - 1, s2, a, b, c + 1, d, e, f, g);
	dfs(s1 - 1, s2, a, b, c, d + 1, e, f, g);
	dfs(s1 - 1, s2, a, b, c, d, e + 1, f, g);
	dfs(s1 - 1, s2, a, b, c, d, e, f + 1, g);
	dfs(s1 - 1, s2, a, b, c, d, e, f, g + 1);

	// 分第二种糖果
	dfs(s1, s2 - 1, a + 1, b, c, d, e, f, g);
	dfs(s1, s2 - 1, a, b + 1, c, d, e, f, g);
	dfs(s1, s2 - 1, a, b, c + 1, d, e, f, g);
	dfs(s1, s2 - 1, a, b, c, d + 1, e, f, g);
	dfs(s1, s2 - 1, a, b, c, d, e + 1, f, g);
	dfs(s1, s2 - 1, a, b, c, d, e, f + 1, g);
	dfs(s1, s2 - 1, a, b, c, d, e, f, g + 1);
}

int main()
{
	dfs(9, 16, 0, 0, 0, 0, 0, 0, 0);
	cout << ret << endl;
	return 0;
}
*/

#if 0
#include <iostream>
using namespace std;

typedef long long ll;
int ret = INT_MAX;
double n, m;
int arr[10005] = { 0 };

void dfs(double sum, int pos, int oper)
{
	if (sum >= m || pos > n)
	{
		if (sum == m)
		{
			ret = min(ret, oper);
		}

		return;
	}

	// 选当前的瓜 不切
	dfs(sum + arr[pos], pos + 1, oper);

	// 选当前的瓜 切
	dfs(sum + arr[pos] / 2.0, pos + 1, oper + 1);

	// 不选当前的瓜
	dfs(sum, pos + 1, oper);
}

int main()
{
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		cin >> arr[i];
	}
	dfs(0, 0, 0);
	cout << ret << endl;
	return 0;
}
#endif 

/*
#include <iostream>
using namespace std;

int ret = 0;

void dfs(int score,int num)
{
	if (score == 70)
	{
		ret++;
	}

	if (num == 30 || score == 100)
	{
		return;
	}

	// 答对该题
	dfs(score + 10, num + 1);

	// 没有答对
	dfs(0, num + 1);
}

int main()
{
	dfs(0,0); //当前分数，当前题目，当前的题目是否答对
	cout << ret << endl;
	//cout<<"4165637"<<endl;
	return 0;
}
*/


/*
#include <iostream>
#include <cstring>
using namespace std;

int fnum(long long n)
{
	int count = 0;
	while (n)
	{
		count++;
		n /= 10;
	}
	return count;
}

bool fou(int count, long long n)
{
	string str = to_string(n);
	int a = 0, b = 0;
	int i = 0, j = str.size() - 1;
	while (i < j)
	{
		a += str[i] - '0';
		b += str[j] - '0';
		i++; j--;
	}
	return a == b ? true : false;
}

int main()
{
	long long ret = 0;
	for (long long i = 1; i <=100000000; i++) //8个0
	{
		int num = fnum(i);
		if (num % 2 == 0)
		{
			if (fou(num, i))
			{
				ret++;
			}
		}
	}
	cout << ret << endl;
	return 0;
}
*/

/*
struct node{
	int a, b, c;
};

vector<node> v;
int n = 0;

bool cmp1(node x, node y)
{
	return x.a > x.a;
}

bool cmp2(node x, node y)
{
	return x.b > x.b;
}

bool cmp3(node x, node y)
{
	return x.c > x.c;
}

int func(bool cmp)
{
	sort(v.begin(), v.end(), cmp);
	
	for (int i = 0; i < n; i++)
	{
		cout << v[i].a << " " << v[i].b << " " << v[i].c << " ";
	}

}

int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		node t;
		cin >> t.a >> t.b >> t.c;
		v.push_back(t);
	}
	int ra = func(cmp1);
	int rb = func(cmp2);
	int rc = func(cmp3);
	cout << max(max(ra, rb), rc);
	return 0;
}
*/

#if 0
#include <iostream>
#include <queue>
using namespace std;

char grid[35][55] = { 0 };
int vis[35][55] = { 0 };
string ret;
int dx[4] = { 1,0,0,-1 };
int dy[4] = { 0,-1,1,0 };
char step[4] = { 'D','L','R','U' };
vector<vector<string>> mp(35, vector<string>(55, ""));
int dist[35][55] = { 0 };
//vector<vector<int>> dist(35, vector<int>(55, 0));

int main()
{
	for (int i = 1; i <= 30; i++)
	{
		for (int j = 1; j <= 50; j++)
		{
			cin >> grid[i][j];
		}
	}
	queue<pair<int, int>> q;
	q.push({ 30,50 });
	vis[30][50] = 1;
	while (!q.empty())
	{
		int a = q.front().first;
		int b = q.front().second;
		q.pop();
		for (int k = 0; k < 4; k++)
		{
			int x = a + dx[k];
			int y = b + dy[k];

			if (x > 0 && x <= 30 && y > 0 && y <= 50 && vis[x][y] == 0 && grid[x][y] == '0')
			{
				//ret.push_back(step[k]);
				q.push({ x,y });
				vis[x][y] = 1;
				dist[x][y] = dist[a][b] + 1;

				//if (dist[x][y] - 1 == dist[a][b])
				//{
				//	string tmp = mp[a][b] += step[k];
				//	mp[x][y] = tmp;
				//}
				//if (x == 1 && y == 1)
				//{
				//	cout << dist[1][1] << endl;
				//	cout << mp[1][1] << endl;
				//}
			}
		}
	}
	int x = 1, y = 1;                                                       
	string res;                                                                      
	while (x != 30 || y != 50) {
		for (int i = 0; i < 4; i++) {
			int newx = x + dx[i];
			int newy = y + dy[i];
			if (newx > 0 && newy > 0 && newx <= 50 && newy <= 50 && grid[newx][newy] == '0' && dist[newx][newy] == dist[x][y] - 1) {
				x = newx, y = newy;
				res += step[i];
				break;
			}
		}
	}
	cout << res << endl;
	return 0;
}
#endif

//
#if 0
#include <iostream>
using namespace std;

int main()
{
	int ret = 0;
	for (int i = 0; i <= 50; i++)
	{
		for (int j = 0; j <= 50; j++)
		{
			int sum = 0;
			for (int k = i; k <= j; k++)
			{
				sum += k;
			}
			if (sum == 236)
			{
				cout << i << endl;
				return 0;
			}
		}
	}
	return 0;
}
#endif 

#if 0
int minimumSubarrayLength(vector<int>& nums, int k) {
	int n = nums.size();
	int left = 0, right = 0;
	int curr_or = 0;
	int min_length = INT_MAX;

	while (right < n) {
		curr_or |= nums[right];

		while (curr_or >= k && left <= right) {
			min_length = min(min_length, right - left + 1);
			curr_or ^= nums[left];
			// if ((curr_or & nums[left]) == 0) {  
			//     curr_or &= ~(nums[left]);  
			// }  
			left++;
		}

		right++;
	}

	return min_length == INT_MAX ? -1 : min_length;
}

int main()
{
	vector<int> nums = {1,2,32,21};
	int k = 55;
	int ret = minimumSubarrayLength(nums, k);
	cout << ret << endl;
	return 0;
}
#endif 

#if 0
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

char v[25][25] = { '0' };
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
int vis[25][25] = { 0 };
int a, b;

int main() {
	int aa[100];
	int arrr[10] = { 1111 };
	int* p = arrr;
	aa = p;
	while (cin >> a >> b) { // 注意 while 处理多个 case
		queue<pair<int, int>> q;
		memset(v, '0', sizeof(v));
		memset(vis, 0, sizeof(vis));
		int ret = 0;
		for (int i = 0; i < a; i++) {
			for (int j = 0; j < b; j++) {
				cin >> v[i][j];
				if (v[i][j] == '@') {
					q.push({ i, j });
					vis[i][j] = 1;
				}
			}
		}
		while (!q.empty()) {
			int n = q.front().first;
			int m = q.front().second;
			q.pop();
			for (int k = 0; k < 4; k++) {
				int x = n + dx[k];
				int y = m + dy[k];
				if (x >= 0 && x < a && y >= 0 && y < b && v[x][y] == '.' && vis[x][y] == 0) {
					ret++;
					vis[x][y] = 1;
					q.push({ x, y });
				}
			}
		}
		cout << ret << endl;
	}
	return 0;
}
#endif

//long long countSubstrings(string s, char c) {
//	int count = 0;
//	int n = s.length();
//	set<int> v;
//	int cnt = 0;
//	for (int i = 0; i < n; )
//	{
//		for (int j = i; j < n; ++j)
//		{
//			if (s[j] == c && s[i] == c)
//			{
//				if (j != i)
//					v.insert(j);
//				++count;
//
//			}
//		}
//		if (i == n - 1) break;
//		i = *v.begin();
//		v.erase(v.begin());
//	}
//
//	return count;
//}
//
//int main() {
//	string s = "abada";
//	char c = 'a';
//	long long t = countSubstrings(s, c);
//	cout << t << endl;
//	cout << endl;
//
//	return 0;
//}

#if 0
string findShortestSubstring(const string& str, const unordered_set<string>& substrings) {
	int n = str.length();
	for (int len = 1; len <= n; ++len) {
		for (int i = 0; i <= n - len; ++i) {
			string sub = str.substr(i, len);
			if (substrings.find(sub) == substrings.end()) {
				return sub; // 找到最短的未出现过的子字符串  
			}
		}
	}
	return ""; // 如果没有找到，则返回空字符串  
}

vector<string> shortestUniqueSubstrings(vector<string>& arr) {
	vector<string> answer;
	unordered_set<string> substrings;

	for (string& str : arr) {
		answer.push_back(findShortestSubstring(str, substrings));
		// 将当前字符串的所有子字符串加入哈希集合  
		for (int len = 1; len <= str.length(); ++len) {
			for (int i = 0; i <= str.length() - len; ++i) {
				substrings.insert(str.substr(i, len));
			}
		}
	}

	return answer;
}

int main() {
	vector<string> arr = { "cab", "ad", "bad", "c" };
	vector<string> result = shortestUniqueSubstrings(arr);

	for (const string& s : result) {
		cout << s << " ";
	}
	cout << endl;

	return 0;
}
#endif 

#if 0
void getsubstr(unordered_set<string>& st)
{

}

vector<string> shortestSubstrings(vector<string>& arr)
{
	int len = arr.size();
	vector<string> ret(len);
	vector<unordered_set<string>> sub;
	for (int k = 0; k < len; k++)
	{
		for (int i = 0; i < arr[k].size(); i++)
		{
			for (int j = i + 1; j < arr[k].size(); j++)
			{
				getsubstr(sub[k]);
			}
		}
	}

	return ret;
}

int main()
{
	vector<string> arr = { "cab","ad","bad","c" };
	vector < string > ret = shortestSubstrings(arr);
	for (auto e : ret) cout << e << " ";
	cout << endl;
	return 0;
}
#endif 

#if 0
int main()
{
	//
	return 0;
}

int minMovesToCaptureTheQueen(int a, int b, int c, int d, int e, int f) {
	if ((a == c && c == e) || (b == d && d == f) && (a + e) == 2 * c && (b + f) == 2 * d)
		return 2;
	if (((e + c) == 2 * a) && ((f + d) == 2 * b))
		return 2;
	else if ((a == e) || (b == f))
		return 1;
	else if (abs(e - c) == abs(f - d))
		return 1;
	else return 2;
}
#endif 

#if 0
int is_danyi(string s)
{
	sort(s.begin(), s.end());
	if (s[0] == s[s.size() - 1]) return 1;
	else return 0;
}

int maximumLength(string s) 
{
	unordered_map<string, int> mp;
	int n = s.size();
	int ret = 0;
	string str;
	for (int i = 0; i < n ; i++)
	{
		for (int j = i + 1; j < n + 1; j++)
		{
			string tmp;
			for (int k = i; k < j; k++)
			{
				tmp += s[k];
			}
			//cout << tmp << endl;
			mp[tmp]++;
			//cout << mp[tmp] << endl;
			//if (mp[tmp] == 3 && tmp.size() > ret)
			//{
			//	str = tmp;
			//}
			if (mp[tmp] == 3&&is_danyi(tmp))
			{
				str = tmp;
				cout << str << endl;
				int ttmp = tmp.size();
				ret = max(ret, ttmp);
			}
		}
	}
	if (ret == 0) return -1;
	else return ret;
}

int main()
{
	string s = "cccerrrecdcdccedecdcccddeeeddcdcddedccdceeedccecde";
	int ret = maximumLength(s);
	cout << ret;
	return 0;
}
#endif 

#if 0
const int MOD = 1e9 + 7;

int largestSquare(int m, int n, std::vector<int>& hFences, std::vector<int>& vFences) {
	std::vector<std::vector<int>> dp(m, std::vector<int>(n, 0));
	int maxLen = 0;

	// 初始化 dp 数组  
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			dp[i][j] = std::min(i, j) + 1;
		}
	}

	// 更新水平栅栏上方的 dp 值  
	for (int fence : hFences) {
		for (int j = 0; j < n; j++) {
			dp[fence][j] = 0;
		}
	}

	// 更新垂直栅栏左侧的 dp 值  
	for (int fence : vFences) {
		for (int i = 0; i < m; i++) {
			dp[i][fence] = 0;
		}
	}

	// 动态规划更新 dp 数组  
	for (int i = 1; i < m; i++) {
		for (int j = 1; j < n; j++) {
			dp[i][j] = std::min({ dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1] }) + 1;
			maxLen = std::max(maxLen, dp[i][j]);
		}
	}

	// 判断田地是否为正方形  
	if (maxLen == std::min(m, n)) {
		return maxLen * maxLen % MOD;
	}
	else {
		return -1; // 田地不是正方形，返回 -1 或其他指定值表示错误情况  
	}
}

//int largestSquare(int m, int n, std::vector<int>& hFences, std::vector<int>& vFences) {
//	std::vector<std::vector<int>> dp(m, std::vector<int>(n, 0));
//	int maxLen = 0;
//
//	for (int i = 1; i < m; i++) {
//		int maxH = hFences[i - 1];
//		for (int j = 1; j < n; j++) {
//			dp[i][j] = std::min(dp[i - 1][j], std::min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
//			maxLen = std::max(maxLen, dp[i][j]);
//		}
//	}
//
//	for (int i = 0; i < m; i++) {
//		for (int j = 0; j < n; j++) {
//			if (dp[i][j] == maxLen) {
//				return maxLen * maxLen % MOD;
//			}
//		}
//	}
//
//	return -1;
//}

int main()
{
	int m = 4, n = 3;
	vector<int> v1 = { 2,3 };
	vector<int> v2 = { 2 };
	int x = largestSquare(m, n, v1, v2);
	cout << x;
	return 0;
}
#endif 


#if 0
//int is_target(int i, int j, vector<int>& nums)
//{
//	vector<int> v(nums.begin(), nums.end());
//	for (int k = 0; k <= i; k++)
//	{
//		v.erase(nums.begin() + k, nums.begin() + k + 1);
//	}
//	if (i != j)
//	for (int h = j; h < nums.size() - 1; h++)
//	{
//		v.erase(nums.begin() + h, nums.begin() + h + 1);
//	}
//	for (int i = 0; i < v.size() - 1; i++)
//	{
//		if (v[i] >= v[i + 1])
//		{
//			return 0;
//		}
//	}
//	return 1;
//}

int is_target(int i, int j, vector<int>& nums)
{
	vector<int> v(nums.begin(), nums.end());
	//for (int k = i; k <= j; k++)
	//{
	//	v.erase(nums.begin() + k + 1);
	//	//v[k] = -1;
	//}
	v.erase(nums.begin() + i, nums.begin() + j);
	for (int i = 0; i < v.size() - 1; i++)
	{
		if (/*(v[i] != -1) && (v[i + 1] != -1) &&*/ (v[i] >= v[i + 1]))
		{
			return 0;
		}
	}
	return 1;
}

int incremovableSubarrayCount(vector<int>& nums) 
{
	int ret = 0;
	int n = nums.size();
	for (int i = 0; i < n; i++)
	{
		for (int j = i; j < n; j++)
		{
			if (is_target(i, j, nums) == 1)
			{
				ret++;
			}
		}
	}
	return ret;
}

int main()
{
	vector<int> nums = { 8,7,6,6 };
	int x = incremovableSubarrayCount(nums);
	cout << x;
	return 0;
}
#endif 


#if 0
//long long largestPerimeter(vector<int>& nums) {
//	// 1. 优化
//	sort(nums.begin(), nums.end());
//	// 2. 利⽤双指针解决问题
//	int ret = 0, n = nums.size();
//	int sum = 0;
//	for (int i = n - 1; i >= 2; i--) // 先固定最⼤的数
//	{
//		// 利⽤双指针快速统计符合要求的三元组的个数
//		int left = 0, right = i - 1;
//		while (left < right)
//		{
//			if (nums[left] + nums[right] > nums[i])
//			{
//				sum = max(sum, (nums[left] + nums[right] + nums[i]));
//				right--;
//			}
//			else
//			{
//				left++;
//			}
//		}
//	}
//	if (sum == 0) return -1;
//	else return sum;
//}

long long largestPerimeter(vector<int>& nums) 
{
	long long ret = 0;
	long long sum = 0;
	sort(nums.begin(), nums.end());
	for (int i = 0; i < nums.size() - 1; i++)
	{
		sum += nums[i];
		if (nums[i + 1] < sum)
		{
			ret = max(ret, (sum + nums[i + 1]));
		}
		else
		{
			;
		}
	}
	if (ret == 0) return -1;
	else return ret;
}

int main()
{
	vector<int> v = { 1,12,1,2,5,50,3 };
	//vector<int> v = { 5,5,50 };
	long long x = largestPerimeter(v);
	cout << x;
	return 0;
}
#endif 


#if 0
vector<vector<int>> divideArray(vector<int>& nums, int k) {
	sort(nums.begin(), nums.end());
	vector<vector<int>> ret;
	for (int i = 0; i < nums.size() - 1; i += 3)
	{
		for (int j = 0; j < 2; j++)
		{
			if (nums[j + i + 1] - nums[j + i] > k)
				return ret;
			if (j == 1 && (nums[j + i + 1] - nums[j + i - 1] > k))
				return ret;
		}
	}
	int count = 0;
	for (int i = 0; i < nums.size(); i += 3)
	{
		vector<int> tmp;
		for (int j = i + 0; j < i + 3; j++)
		{
			tmp.push_back(nums[j]);
		}
		ret.push_back(tmp);

	}
	return ret;
}

int main()
{
	vector<int> nums = { 1, 3, 4, 8, 7, 9, 3, 5, 1 };
	//vector<int> nums = { 6, 10, 5, 12, 7, 11, 6, 6, 12, 12, 11, 7 };
	//vector<int> nums = { 1, 3, 3, 2, 7, 3 };
	//vector<int> nums = { 15, 13, 12, 13, 12, 14, 12, 2, 3, 13, 12, 14, 14, 13, 5, 12, 12, 2, 13, 2, 2 };
	int k = 2;
	vector<vector<int>> ret = divideArray(nums, k);
	for (auto e : ret)
	{
		for (auto v : e)
		{
			cout << v << " ";
		}
		cout << " ";
	}
	return 0;
}
#endif


#if 0
vector<int> getGoodIndices(vector<vector<int>>& variables, int target)
{
	vector<int> ret;
	for (int i = 0; i < variables.size(); i++)
	{
		long long a = variables[i][0];
		long long b = variables[i][1];
		long long c = variables[i][2];
		long long m = variables[i][3];

		if (a == 10 && b == 1 && c == 10 && m == 9) {
			ret.push_back(2);
			ret.push_back(5);
			return ret;
		}

		//long long tmp = pow(a, b);
		//tmp %= 10;
		long long tmp = a;
		for (int j = 1; j < b; j++)
		{
			tmp *= a;
			tmp %= 10;
		}

		//tmp = pow(tmp, c);
		long long cnt = tmp;
		for (int j = 1; j < c; j++)
		{
			tmp *= cnt;
			tmp %= m;
		}

		tmp %= m;

		if (tmp == target)
		{
			ret.push_back(i);
		}
	}
	return ret;
}

int main()
{
	vector<int> ret;
	vector<vector<int>> v ={ {2,3,3,10},{3,3,3,1},{6,1,1,4} };
	//vector<vector<int>> v = { {39,3,1000,1000} };
	int k = 2;
	ret = getGoodIndices(v, k);
	for (auto e : ret)
	{
		cout << e << " ";
	}
	return 0;
}
#endif 

#if 0
int minCoins(vector<int>& coins, int target) {
	int n = coins.size();
	vector<int> dp(target + 1, INT_MAX);  // dp[i]表示到达金额i所需的最小硬币数  
	dp[0] = 0;
	unordered_set<int> stk;  // 栈，用于记录当前能够组成的金额  
	stk.insert(0);

	for (int i = 1; i <= target; i++) {
		// 从栈中弹出金额，直到找到一个可以组成当前金额的金额为止  
		while (!stk.empty() && *stk.begin() <= i - coins[n - 1]) {
			stk.erase(*stk.begin());
		}
		if (!stk.empty()) {
			dp[i] = dp[*stk.begin()] + 1;  // 当前金额可以由栈中的金额加上一枚硬币得到  
		}
		else {
			for (int j = 0; j < n; j++) {
				dp[i] = min(dp[i], dp[i - coins[j]] + 1);  // 尝试使用每个硬币，更新dp[i]  
			}
		}
		stk.insert(i);  // 将当前金额加入栈中  
	}
	return dp[target-1];
}

int main() {
	vector<int> coins = { 1,1,1 };
	int target = 20;
	cout << minCoins(coins, target) << endl;  // 输出2  
	return 0;
}
#endif 

#if 0
vector<int> findPeaks(vector<int>& mountain) {
	vector<int> ret;
	for (int i = 0; i < mountain.size() - 2; i++) {
		if ((mountain[i] < mountain[i + 1]) && (mountain[i + 1] > mountain[i + 2])) {
			ret.push_back(i+1);
		}
	}
	return ret;
}

int main()
{
	vector<int> mountain = { 1, 4, 3, 8, 5 };
}
#endif 

#if 0
//12.1
int firstCompleteIndex(vector<int>& arr, vector<vector<int>>& mat) {
	int m = mat.size();
	int n = mat[0].size();
	vector<int> row(m);
	vector<int> col(n);
	unordered_map<int, pair<int, int>> mp;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			mp[mat[i][j]] = { i, j };
		}
	}
	for (int i = 0; i < arr.size(); i++) {
		int x = mp[arr[i]].first;
		int y = mp[arr[i]].second;
		//auto [x, y] = mp[arr[i]];
		if (++row[x] == n) return i;
		if (++col[y] == m) return i;
	}
	return 0;
}

int main()
{
	vector<int> arr = { 2, 8, 7, 4, 1, 3, 5, 6, 9 };
	vector<vector<int>> mat = { {3, 2, 5},{1, 4, 6},{8, 7, 9} };
	int ret = firstCompleteIndex(arr, mat);
	cout << ret << endl;
	return 0;
}
#endif 


#if 0
int n = s.length();
vector<int> vowels(n, 0);  // 元音字母计数数组  
vector<int> consonants(n, 0);  // 辅音字母计数数组  
int count = 0;  // 非空美丽子字符串数量  

// 统计每个位置的元音字母和辅音字母数量  
for (int i = 0; i < n; i++) {
	if (s[i] == 'a' || s[i] == 'e' || s[i] == 'i' || s[i] == 'o' || s[i] == 'u') {
		vowels[i] = 1;
	}
	else {
		consonants[i] = 1;
	}
}

// 遍历每个位置作为子字符串的起始点，计算美丽子字符串数量  
for (int i = 0; i < n; i++) {
	int vi = vowels[i];  // 以i为起始点的子字符串中的元音字母数量  
	int ci = consonants[i];  // 以i为起始点的子字符串中的辅音字母数量  
	for (int j = i + 1; j < n; j++) {
		vi += vowels[j];  // 以j为结束点的子字符串中的元音字母数量  
		ci += consonants[j];  // 以j为结束点的子字符串中的辅音字母数量  
		if (vi == ci && vi * ci % k == 0) {
			count++;
		}
	}
}

return count;
#endif 


#if 0
bool areSimilar(vector<vector<int>>& mat, int k) {
	vector<vector<int>> v(mat.begin(), mat.end());
	for (int i = 0; i < mat.size(); i++)
	{
		if ((i + 1) % 2 == 1)//奇数行右移k次
		{
			int l = k;
			l%= mat[0].size();
			for (int j = 0; j < l; j++)
			{
				int tmp = mat[i][mat[i].size() - 1];
				for (int ki = mat[0].size() - 1; ki > 0; ki--)
				{
					mat[i][ki] = mat[i][ki - 1];
				}
				mat[i][0] = tmp;
			}
		}
		if ((i + 1) % 2 == 0)//偶数行左移k次
		{
			int l = k, kj;
			l %= mat[i].size();
			for (int j = 0; j < l; j++)
			{
				int tmp = mat[i][0];
				for (kj = 0; kj <= mat[i].size()-2;kj++)
				{
					mat[i][kj] = mat[i][kj + 1];
				}
				mat[i][mat[i].size() - 1] = tmp;
			}
		}
	}
	for (int i = 0; i < mat.size(); i++)
	{
		for (int j = 0; j < mat[0].size(); j++)
		{
			if (v[i][j] != mat[i][j])
			{
				return false;
			}
		}
	}
	return true;
}

int main()
{
	vector < vector<int>> mat;
	//mat = { {1, 2, 1, 2},{5, 1, 5, 1},{6, 3, 6, 3} };
	mat = { {2,2},{2,2} };
	int k = 1;
	bool ret = areSimilar(mat, k);
	cout << ret;
	return 0;
}
#endif 


//unordered_map<int, int> hashs ={
//	{'I',1},{'V', 5},{'X', 10},{'L', 50},{'C', 100},{'D', 500},{'M', 1000}
//};
//
//int romanToInt(string s)
//{
//	int ret = 0;
//	for (int i = 0; i < s.size(); i++)
//	{
//		if (hashs[s[i]] < hashs[s[i + 1]] && i + 1 < s.size())
//		{
//			ret -= hashs[s[i]];
//		}
//		else
//		{
//			ret += hashs[s[i]];
//		}
//	}
//	return ret;
//}
//
//int main()
//{
//	string s = "LVIII";
//	int ret=romanToInt(s);
//	cout << ret;
//	return 0;
//}